package Year21_Month11.day1113;



import java.util.Arrays;

public class MyPriorityQueue {
    Integer[] array;//构造新数组
    int size;//记录有效元素个数

    public MyPriorityQueue(){
        array = new Integer[11];//初始容量大小设置为11
        size = 0;
    }
    public MyPriorityQueue(int k){
        if(k < 0){
            throw new IllegalArgumentException("初始容量异常");
        }
        array = new Integer[k];
        size = 0;
    }
//=======================================================================================
    //关于向上调整
    public void shiftUp(int child){
        int parent = (child - 1) / 2;//定义双亲节点
        while(child != 0){
            if(array[child] < array[parent]){//小根堆，如果父母节点值比自己大，那么双方交换
                swap(child,parent);
                child = parent;//交换成功之后，child节点变为原来的parent节点
                parent = (child - 1) / 2;
            }else{
                return;
            }
        }
    }
    //关于交换的方法
    public  void swap(int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //关于向下调整
    public void shiftDown(int parent){
        int child = parent * 2+1;//这里直接定义做孩子
        //首先它肯定有左孩子，并且左孩子不能越界
        while(child < size){
            //如果它有右孩子的值更小，那么就和右孩子进行交换
            if(child + 1 < size && array[child + 1] < array[child]){
                child = child + 1;
            }
            //这是交换的具体过程
            if(array[child] < array[parent]){
                //注意这里的swap方法就是上面的swap方法
                swap(child,parent);
                parent = child;
                child = parent * 2 + 1;
            }
        }
    }
//============================================================================================

    //关于删除操作
    public Integer poll(){
        if(isEmpty()){
            return null;
        }
        //保存首元素
        Integer key = array[0];
        //交换首位元素位置
        swap(0,size - 1);
        //有效元素个数size--
        size--;
        //向下调整
        shiftDown(0);
        return key;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    //关于插入操作
    public boolean offer(Integer e){
        //先保证传入参数正确
        if(e == null){
            throw new NullPointerException("传入参数有误");
        }
        //扩容
        ensureCapcity();
        //末尾进行插入
        array[size] = e;
        //有效元素个数加一
        size++;
        //向上调整
        shiftUp(size - 1);
        return true;
    }
    //关于扩容
    public void ensureCapcity(){
        if(array.length == size){
            int newCaptity = size * 2;
            array = Arrays.copyOf(array,newCaptity);
        }
    }

    public MyPriorityQueue(Integer[] arr){
        // 1. 将arr中的元素拷贝到数组中
        array = new Integer[arr.length];
        for(int i = 0; i < arr.length; ++i){
            array[i] = arr[i];
        }
        size = arr.length;

        // 2. 找当前完全二叉树中倒数第一个叶子节点
        //    注意：倒数第一个叶子节点刚好是最后一个节点的双亲
        //    最后一个节点的编号size-1  倒数第一个非叶子节点的下标为(size-1-1)/2
        int lastLeafParent = (size-2)/2;

        // 3. 从倒数第一个叶子节点位置开始，一直到根节点的位置，使用向下调整
        for(int root = lastLeafParent; root >= 0; root--){
            shiftDown(root);
        }
    }
}
